#include <stdio.h>
#include <stdlib.h>

#define HEAP_SIZE 256

/* STRUCT qui represente un block de memoire libre */
typedef struct __freeBlock {
	int blockSize;
	char * buffer;
	struct __freeBlock * nextBlock;
	struct __freeBlock * previousBlock;	
} freeBlock;

char * heap;	/* Le tas */
freeBlock * listOfFreeBlocks;	/* Liste de blocks libres */
int countFreeBlocks;	/* Nombre de blocks libres */

/* Initialise le tas et la liste de blocks libres */
int Initialize() {
	heap = (char *)malloc(HEAP_SIZE);
	printf("Heap created\n");
	printf("Heap address is %d\n",heap);
	printf("Heap end address is %d\n",heap+HEAP_SIZE);
	listOfFreeBlocks = (freeBlock *)heap;
	listOfFreeBlocks->nextBlock = listOfFreeBlocks;
	listOfFreeBlocks->previousBlock = listOfFreeBlocks;
	listOfFreeBlocks->blockSize = HEAP_SIZE - sizeof(freeBlock);
	listOfFreeBlocks->buffer = (char *)(listOfFreeBlocks) + sizeof(freeBlock);
	printf("List of free blocks initialised\n");
	countFreeBlocks = 1;
	return 0;
}

/* Alloue une portion de memoire avec la taille passee en parametre */
void * gMalloc(unsigned size) {
	freeBlock * currentBlock = listOfFreeBlocks;
	int countCurrentBlock = 1;
	printf("Call to gMalloc with size = %d\n",size);
	while(countCurrentBlock <= countFreeBlocks) {
		/* Un block de la taille exacte a ete trouve */
		if(currentBlock->blockSize == size) {
			/* Le block a allouer est le seul bloc libre */
			if(countFreeBlocks == 1) {
				listOfFreeBlocks == NULL;
			}
			/* Le block a allouer n'est pas le seul bloc libre */
			else {
				currentBlock->nextBlock->previousBlock == currentBlock->previousBlock;
				currentBlock->previousBlock->nextBlock == currentBlock->nextBlock;
				if(countCurrentBlock == 1) {
					listOfFreeBlocks == currentBlock->nextBlock;
				}
			}
			printf("gMalloc: a block with the exact size was found\n");
			countFreeBlocks--;
			return currentBlock->buffer;	
		}
		/* Un block d'une taille plus grande a ete trouve */
		else if(currentBlock->blockSize > size+sizeof(freeBlock)) {
			/* Le block a allouer est le seul bloc libre */
			if(countFreeBlocks == 1) {
				listOfFreeBlocks = (freeBlock *)((char *)currentBlock+sizeof(freeBlock)+size);
				listOfFreeBlocks->blockSize = currentBlock->blockSize-size-sizeof(freeBlock);
				listOfFreeBlocks->buffer = (char*)(listOfFreeBlocks)+sizeof(freeBlock);
				listOfFreeBlocks->nextBlock = listOfFreeBlocks;
				listOfFreeBlocks->previousBlock = listOfFreeBlocks;
			}
			/* Le block a allouer n'est pas le seul bloc libre */
			else {
				freeBlock * newBlock = (freeBlock *)((char *)currentBlock+sizeof(freeBlock)+size);
				newBlock->nextBlock = currentBlock->nextBlock;
				newBlock->previousBlock = currentBlock->previousBlock;
				newBlock->blockSize = currentBlock->blockSize-size-sizeof(freeBlock);
				newBlock->buffer = (char *)(newBlock)+sizeof(freeBlock);
				newBlock->previousBlock->nextBlock = newBlock;
				newBlock->nextBlock->previousBlock = newBlock;
			}
			printf("gMalloc: a block with a greater size was found\n");
			currentBlock->blockSize = size;
			return currentBlock->buffer;
		}
		countCurrentBlock++;
		currentBlock = currentBlock->nextBlock;
	}
	printf("Error: gMalloc could not allocate memory\n" );
	return NULL;
}

/* Libere une portion de memoire allouee precedemment */
void gFree(void * ptr) {
	printf("Call to gFree\n");
	freeBlock * newBlock;
	/* Le pointeur passe en parametre est NULL */
	if(ptr == NULL) {
		printf("ERROR: NULL pointer\n");
		return;
	}
	newBlock = (freeBlock *)((char *)ptr-sizeof(freeBlock));
	printf("Block header's address is %d\n",newBlock);
	/* Le pointeur passe en parametre pointe vers une adresse invalide */
	if(newBlock < heap || newBlock > heap+HEAP_SIZE) {
		printf("ERROR: invalid pointer\n");
		return;
	}
	/* La liste de blocs libres est vide */
	if(countFreeBlocks == 0) {
		listOfFreeBlocks = newBlock;
		listOfFreeBlocks->nextBlock = listOfFreeBlocks;
		listOfFreeBlocks->previousBlock = listOfFreeBlocks;
		countFreeBlocks++;
		return;
	}
	else {
		/* Le block est a inserer au debut de la liste */
		if(newBlock < listOfFreeBlocks) {
			/* Le bloc a inserer est a cote du premier bloc de la liste - les deux sont fusionnes */
			if((freeBlock *)((char *)newBlock+sizeof(freeBlock)+newBlock->blockSize) == listOfFreeBlocks) {
				newBlock->nextBlock = listOfFreeBlocks->nextBlock;
				newBlock->previousBlock = listOfFreeBlocks->previousBlock;
				newBlock->blockSize = newBlock->blockSize + sizeof(freeBlock) + listOfFreeBlocks->blockSize;
				listOfFreeBlocks = newBlock;
				newBlock->previousBlock->nextBlock = newBlock;
				newBlock->nextBlock->previousBlock = newBlock;
			}
			else {
				newBlock->nextBlock = listOfFreeBlocks;
				newBlock->previousBlock = listOfFreeBlocks->previousBlock;
				listOfFreeBlocks = newBlock;
				newBlock->previousBlock->nextBlock = newBlock;
				newBlock->nextBlock->previousBlock = newBlock;
				countFreeBlocks++;
			}
			return;
		}
		/* Le block est a inserer a la fin de la liste */
		else if(newBlock > listOfFreeBlocks->previousBlock) {
			/* Le bloc a inserer est a cote du dernier bloc de la liste - les deux sont fusionnes */
			if((freeBlock *)((char *)listOfFreeBlocks->previousBlock+sizeof(freeBlock)+listOfFreeBlocks->previousBlock->blockSize) == newBlock) {
				listOfFreeBlocks->previousBlock->blockSize = listOfFreeBlocks->previousBlock->blockSize + sizeof(freeBlock) + newBlock->blockSize;
			}
			else {
				newBlock->nextBlock = listOfFreeBlocks;
				newBlock->previousBlock = listOfFreeBlocks->previousBlock;
				newBlock->previousBlock->nextBlock = newBlock;
				newBlock->nextBlock->previousBlock = newBlock;
				countFreeBlocks++;
			}
			
			return;
		}
		/* Le block est a inserer au milieu de la liste */
		else {
			freeBlock * currentBlock = listOfFreeBlocks;
			int countCurrentBlock = 1;
			while(countCurrentBlock < countFreeBlocks) {
				if(newBlock > currentBlock && newBlock < currentBlock->nextBlock) {
					/* Le bloc a inserer est entre deux blocs libres - les trois blocs sont fusionnes */
					if(((freeBlock *)((char *)currentBlock+sizeof(freeBlock)+currentBlock->blockSize) == newBlock) &&
					   ((freeBlock *)((char *)newBlock+sizeof(freeBlock)+newBlock->blockSize) == currentBlock->nextBlock)) {
						int temp = currentBlock->nextBlock->blockSize;
						currentBlock->nextBlock = currentBlock->nextBlock->nextBlock;
						currentBlock->nextBlock->previousBlock = currentBlock;
						currentBlock->blockSize = currentBlock->blockSize + 2*sizeof(freeBlock) + temp + newBlock->blockSize;
						countFreeBlocks--;
					}
					/* Le bloc a inserer est a cote d' un bloc libre - les deux sont fusionnes */
					else if((freeBlock *)((char *)currentBlock+sizeof(freeBlock)+currentBlock->blockSize) == newBlock) {
						currentBlock->blockSize = currentBlock->blockSize + sizeof(freeBlock) + newBlock->blockSize;
					}
					/* Le bloc a inserer est a cote d'un bloc libre - les deux sont fusionnes */
					else if((freeBlock *)((char *)newBlock+sizeof(freeBlock)+newBlock->blockSize) == currentBlock->nextBlock) {
						newBlock->nextBlock = currentBlock->nextBlock->nextBlock;
						newBlock->previousBlock = currentBlock;
						newBlock->blockSize = newBlock->blockSize + sizeof(freeBlock) + currentBlock->nextBlock->blockSize;
						newBlock->nextBlock->previousBlock = newBlock;
						currentBlock->nextBlock = newBlock;
					}
					/* Le bloc a inserer n'est pas adjacent a un bloc libre */
					else {
						newBlock->nextBlock = currentBlock->nextBlock;
						newBlock->previousBlock = currentBlock;
						currentBlock->nextBlock = newBlock;
						newBlock->nextBlock->previousBlock = newBlock;
						countFreeBlocks++;
					}
					return;
				}
				countCurrentBlock++;
				currentBlock = currentBlock->nextBlock;
			}
		}
	}
	printf("Critical error: gFree could not find free block emplacement\n" );
}

/* Affiche les informations sur les blocks libres */
int PrintListOfFreeBlocks() {
	freeBlock * currentBlock = listOfFreeBlocks;
	int countCurrentBlock = 1;
	printf("------------------------------------------------------------\n");
	while(countCurrentBlock <= countFreeBlocks) {
		printf("BLOCK\n");
		printf("Block's size is %d\n",currentBlock->blockSize);
		printf("Block's header address is %d\n",currentBlock);
		printf("Block header's end address is %d\n",(char *)currentBlock+sizeof(freeBlock));
		printf("Block's address is %d\n",currentBlock->buffer);
		printf("Block end's address is %d\n",currentBlock->buffer+currentBlock->blockSize);
		countCurrentBlock++;
		currentBlock = currentBlock->nextBlock;
	}
	printf("------------------------------------------------------------\n");
}

